import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/25 9:24
 * @description 不考虑数组大小，可以使用 哈希表存储nums中相同元素的下标，然后随机一个、
 * 但是若文件太大，可能会 MLE，因为开辟了map
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    Map<Integer, List<Integer>> pos;
    Random random;

    public Solution2(int[] nums) {
        pos = new HashMap<Integer, List<Integer>>();
        random = new Random();
        for (int i = 0; i < nums.length; ++i) {
            pos.putIfAbsent(nums[i], new ArrayList<Integer>());
            pos.get(nums[i]).add(i);
        }
    }

    public int pick(int target) {
        List<Integer> indices = pos.get(target);
        return indices.get(random.nextInt(indices.size()));
    }

}
